package maxflow;

import java.util.ArrayList;

public class Graphflow {

    static class point {

        int x;
        int y;

        public point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getRes() {
            return y - x;
        }
        public void add(int a){
            x+=a;
        }
    }

    static class Node {

        ArrayList<Integer> nodes = new ArrayList<Integer>();
        ArrayList<point> capacity = new ArrayList<point>();
        boolean marked = false;

        public Node() {
        }

        public void add(int n, int x, int y) {
            nodes.add(n);
            capacity.add(new point(x, y));
        }
    };
    private ArrayList<Node> lGraph = new ArrayList<Node>();
    private int minarc;
    private ArrayList<Integer> path;

    public Graphflow() {
    }

    public void add() {
        lGraph.add(new Node());
    }

    public void addArc(int n, int m, int x, int y) {
        lGraph.get(n).add(m, x, y);
    }

    public boolean getPath(int n, int min, int index) {
        path.add(n);
        if (n == lGraph.size() - 1) {
            minarc = min;
            return true;
        } else {
            boolean b = false;
            lGraph.get(n).marked = true;
            for (int i = 0; i < lGraph.get(n).nodes.size(); i++) {
                if (!lGraph.get(lGraph.get(n).nodes.get(i)).marked && lGraph.get(n).capacity.get(i).getRes() > 0) {
                    if (lGraph.get(n).capacity.get(i).getRes() < min) {
                        b = b || getPath(lGraph.get(n).nodes.get(i), lGraph.get(n).capacity.get(i).getRes(), index + 1);
                    } else {
                        b = b || getPath(lGraph.get(n).nodes.get(i), min, index + 1);
                    }
                }
                if (b) {
                    i = lGraph.get(n).nodes.size();
                }
            }
            lGraph.get(n).marked = false;
            if (!b) {
                path.remove(index);
            }
            return b;
        }
    }

    public int getFlow() {
        boolean b = true;
        int flow = 0;
        while (b) {
            minarc = Integer.MAX_VALUE;
            path = new ArrayList<Integer>();
            b = getPath(0, Integer.MAX_VALUE, 0);
            if (b) {
                for (int i = 0; i < path.size()-1; i++) {
                    int j = 0;
                    while (lGraph.get(path.get(i)).nodes.get(j) != path.get(i + 1)) {
                        j++;
                    }
                    lGraph.get(path.get(i)).capacity.get(j).add(minarc);
                }
                flow+=minarc;
            }
        }
        return flow;
    }
}
